class Solution
{
public:
    int maxProduct(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> f(n + 1); // f表示最大
        auto g = f;           // g表示最小
        f[0] = g[0] = 1;
        int Max = INT_MIN;
        for (int i = 1; i <= n; ++i)
        {
            // nums[i-1]可能是负数，那么前面最大 * nums[i-2]就为最小了！
            // 如果nums[i-1]是负数，那么f要求最大，就要使用前面最小的数g来 * nums[i-1]就得到一个大的正数
            // 如果nums[i-1]是正数，那么就 nums[i-1]与 nums[i-1]* f[i-1]比较就行，正数*正数 = 正数
            if (nums[i - 1] > 0)
                f[i] = max(nums[i - 1], f[i - 1] * nums[i - 1]);
            else if (nums[i - 1] < 0)
                f[i] = max(nums[i - 1], g[i - 1] * nums[i - 1]);
            // 这里g求的是最小值乘积，如果nums[i-1]是负数，那么要 *f，因为负数 * 正数才能得到一个负数
            // 如果nums[i-1]是正数，那么就*g，因为正数 * 负数才能得到一个负数
            // 这样才保证g是最小值乘积
            if (nums[i - 1] > 0)
                g[i] = min(nums[i - 1], g[i - 1] * nums[i - 1]);
            else if (nums[i - 1] < 0)
                g[i] = min(nums[i - 1], f[i - 1] * nums[i - 1]);
            // f[i] = max(nums[i-1],max(f[i-1]*nums[i-1],g[i-1]*nums[i-1]));
            // g[i] = min(nums[i-1],min(g[i-1]*nums[i-1],f[i-1]*nums[i-1]));
            Max = max(Max, f[i]);
        }
        return Max;
    }
};

class Solution
{
public:
    int numberOfArithmeticSlices(vector<int> &nums)
    {
        if (nums.size() < 3)
            return 0;
        int n = nums.size();
        vector<int> dp(n + 1);
        int count = 0;
        for (int i = 3; i <= n; ++i)
        {
            if (nums[i - 1] - nums[i - 2] == nums[i - 2] - nums[i - 3])
            {
                // dp[i] = 1;
                // dp[i] += dp[i-1];
                dp[i] = dp[i - 1] + 1;
                count += dp[i];
            }
        }
        return count;
    }
};

class Solution
{
public:
    bool wordBreak(string s, vector<string> &wordDict)
    {
        // 前面i-i长度的字符串能被拼接完成，i位置的单词在字典中！就表示完成全部拼接，返回true

        // 优化，查找最后一个单词是否在wordDict中，使用循环遍历时间复杂度比较高，所以可以先将wordDict放到哈希表中
        unordered_set<string> hash;
        for (const auto &e : wordDict)
        {
            hash.insert(e);
        }
        int n = s.size();
        vector<bool> dp(n + 1);
        dp[0] = true; // 保证后续填表是正确的
        s = ' ' + s;  // 让原始字符串下标统一 +1
        for (int i = 1; i <= n; ++i)
        {
            // 加了虚拟空间，所以最后一个单词的起始位置只能到1，不能为0
            for (int j = i; j >= 1; --j) // 最后一个单词的起始下标位置
            {
                // count统计有多少个查找数据，只要不为0，这里就表示最后一个单词能够在wordDict找到
                if (dp[j - 1] == true && hash.count(s.substr(j, i - j + 1)))
                {
                    dp[i] = true;
                    break; // 找到一种就可以了，表示能够拼接
                }
                else
                    dp[i] = false;
            }
        }
        return dp[n];
    }
};

class Solution
{
public:
    int findSubstringInWraproundString(string s)
    {
        int n = s.size();
        vector<int> dp(n, 1); // 字符串s每一个字符必定在base中出现一次
        dp[0] = 1;
        for (int i = 1; i < n; ++i)
        {
            // 如果s[i-1] + 1 == s[i] || (s[i-1] == 'z' && s[i] == 'a')满足任意一种，那么就+dp[i-1]
            if ((s[i - 1] + 1 == s[i]) || (s[i - 1] == 'z' && s[i] == 'a'))
                // 注意这里不是【1 + dp[i-1] + 1 】，因为求的是dp[i]的个数，不是长度，所以我dp[i-1]有3个，if条件成立dp[i]也只有3个
                dp[i] += dp[i - 1]; // 上面初始为1了，所以不用1 + dp[i-1]了
        }
        // 这里，我们不能直接返回dp表最后的dp[n-1]因为可能存在重复数据进行了计算
        // a,b,c   |   a,b,c,d,e  --->>>   我们遇到重复的数据，使用一个26大小数组，下标对应字母a到z
        // 数组每一个位置就来保存字符串s中，每一个字符为结束位置的最多非空子串的值（a,b,c,d,e   必定包含a,b,c进行了去重）
        int hash[26] = {0};
        for (int i = 0; i < n; ++i)
        {
            // 这样一来数组里面存放的就是相应位置的最大值
            hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
        }
        int count = 0;
        for (auto e : hash)
        {
            count += e;
        }
        return count;
    }
};